
\subsection{Problem 4 (11)}

Recommended, 8 Points: Finally, specify the WCET of your library function (third version) as precisely as possible. Your deliverable should include the object code of the WCET-oriented solution, along with a header file which contains the function prototype, as well as your test driver and a documented .ais file for the function. Provide detailed explanations how calls to your function will influence the execution time of the program it is embedded in, how to estimate the functions execution time using measurements, and how to analyze it using aiT. We will evaluate your function (using measurements and aiT), without inspecting the code and without adding any new flow facts. Furthermore, note that in this assignment, LEON3 is
synthesized with an LRU instruction cache; therefore, the execution time may vary depending on the cache state.
\\
\\
\textbf{Solution:}
\\
\\
One can find the documented ``.ais'' file and the documented header file in ``./convex/v3/''. The project file for the tool ``ait'' can also be found in this folder. We were not able to tell the ait tool where to find the loop bound N. So we managed this by annotating manually the source code via the ``.ais'' file.
\\
\\
The parameter N must be known at compile time and should be a data independent value. The only data dependent variable is the pointer to the beginning of the input points array, which must have exactly N 2D-points (point\_t *P), and the pointer to the convex hull array, which must have exactly 2*N 2D-points (point\_t *H).
\\
\\
The WCET of course depends on the value of N. But we define this value as known value at compile time. The 2D-points in the point\_t *P array must be in increasing order of the x coordinates. If there are points which have the same x-coordinates then the points must be sorted according to the y-coordinates in increasing order.
\\
\\
To analyze the code with ait one only has to open the corresponding ait-project. The ``.ais'' file is in the corresponding project included and contains all necessary annotations.
\\
\\
Our test was with a parameter N = 20. We measured about 62000 execution cycles. 
With N = 10 there would be only 62000/5 execution cycles, with N = 40 there would be
62000*5 execution cycles. The length of the execution depends on the four ``for'' loops. An estimation can be done with the following formula:

\begin{equation}
  Cycles = ((N-2)*(N-2)+(N-3)*(N-1)) * 96 
\end{equation}
\begin{equation}
  Cycles(N=20) = 62112
\end{equation}

\noindent This can be seen as first rough estimate to the WCET.
\\
\\
The execution time also depends on the initial instruction cache setting. One has to make sure that the program always starts from the same initial setting to ensure the same sequence of cache hits and misses.